// LeetCode 主站 Problem Nr. 445: 两数相加 II

/*
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：
	输入：l1 = [7,2,4,3], l2 = [5,6,4]
	输出：[7,8,0,7]

示例2：
	输入：l1 = [2,4,3], l2 = [5,6,4]
	输出：[8,0,7]

示例3：
	输入：l1 = [0], l2 = [0]
	输出：[0]

提示：
    链表的长度范围为 [1, 100]
    0 <= node.val <= 9
    输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能翻转该如何解决？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "github.com/saint-yellow/think-leetcode/ds"

type ListNode = ds.SinglyLinkedNode[int]

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	return method1(l1, l2)
}

func convert(n *ListNode) *ListNode {
	if n == nil {
		return n
	}

	var previous *ListNode
	current := n
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}

	return previous
}

func method1(l1, l2 *ListNode) *ListNode {
	l1, l2 = convert(l1), convert(l2)

	l3 := &ListNode{}
	p := l3
	c := 0
	for l1 != nil || l2 != nil || c != 0 {
		v1, v2, v3 := 0, 0, 0
		if l1 != nil {
			v1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			v2 = l2.Val
			l2 = l2.Next
		}
		s := v1 + v2 + c
		if s >= 10 {
			c = 1
			v3 = s - 10
		} else {
			c = 0
			v3 = s
		}

		p.Next = &ListNode{Val: v3}
		p = p.Next
	}
	
	return convert(l3.Next)
}

func method2(l1, l2 *ListNode) *ListNode {
	s1, s2 := make([]int, 0), make([]int, 0)
	for l1 != nil {
		s1 = append(s1, l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		s2 = append(s2, l2.Val)
		l2 = l2.Next
	}

	c := 0
	var l3 *ListNode
	for len(s1) > 0 || len(s2) > 0 || c != 0 {
		v1, v2, v3 := 0, 0, 0
		if len(s1) > 0 {
			v1 = s1[len(s1)-1]
			s1 = s1[:len(s1)-1]
		}
		if len(s2) > 0 {
			v2 = s2[len(s2)-1]
			s2 = s2[:len(s2)-1]
		}
		s := v1 + v2 + c
		if s >= 10 {
			c = 1
			v3 = s - 10
		} else {
			c = 0
			v3 = s
		}

		n := &ListNode{Val: v3, Next: l3}
		l3 = n
	}
	return l3
}
